struct Node
{
    int _val;
    int _key;
    Node* _prev;
    Node* _next;
    Node(int key,int value)
        :_key(key)
        ,_val(value)
        ,_prev(nullptr)
        ,_next(nullptr)
    {}
};

class LRUCache {
public:
    //需要的操作是 
    //1.删除
    //2.将一个数据头插
    LRUCache(int capacity) 
    {
        _capacity=capacity;
        _head=nullptr;
        _tail=nullptr;
    }
    void pushfront(Node* node)
    {
        if(_head==nullptr) 
        {
            node->_next=_head;
            _head=node;
            _head->_prev=_head;
            _tail=_head;
        }
        else
        {
            node->_next=_head;
            _head->_prev=node;
            _head=node;
        }
        // if(_tail==nullptr)
        // {
        //     _tail=_head;
        // }
    }
    void erasenode(Node* node)
    {
        if(_head==node && _tail==node)
        {
            _head=_tail=nullptr;
        }
        else if(_head==node)
        {
            _head=_head->_next;
        }
        else if(_tail==node)
        {
            _tail=_tail->_prev;
        }
        else
        {
            node->_prev->_next=node->_next;
            node->_next->_prev=node->_prev;
        }
    }
    int get(int key) 
    {
        if(_m.find(key)==_m.end()) return -1;
        Node* cur=_m[key];
        erasenode(cur);
        pushfront(cur);
        return cur->_val;
    }
    
    void put(int key, int value) 
    {
        if(_m.find(key)==_m.end())
        {
            //不存在 进行插入
            if(_m.size()>=_capacity)
            {
                //map<int,Node*>::iterator it=_m.find(_tail->_key);
                
                
                //现在表里面删除 因为erasenode有可能会修改_tail指针
                _m.erase(_m.find(_tail->_key));
                erasenode(_tail);
            }
            Node* newnode= new Node(key,value);
            pushfront(newnode);
            _m[key]=newnode;
        }
        else
        {
            Node* change=_m[key];
            change->_val=value;
            erasenode(change);
            pushfront(change);
        }

    }
private:
    Node* _head;
    Node* _tail;
    map<int,Node*> _m;//根据key找节点
    int _capacity;

};
